1. Field of the Invention
The present invention relates to a configuration for interconnecting a plurality of processors on multicomputer or a mesh computer capable of achieving its high speed via a parallel processing on operations by connecting the plurality of processors in a mesh architecture, and communication method for the same. In particular, the present invention relates to a distributed computing system using virtual buses adapted for urgent messages or broadcasting messages transmitting a message to different computers at the same time as well as a point-to-point communication and enabling high speed processing on a large amount of the parallel simulations, real-time programs, or the like by introducing virtual buses into the connection architectures among the processors, and data communication method for the same.
2. Description of the Prior Art
In general, the art of computer is tendentious to a miniaturization and high speed in virtue of semiconductor technologies, thereby providing multicomputer or mesh like and achieving high speed by interconnecting a plurality of processors to effect parallel processing.
The performance of the above-mentioned multicomputer greatly depends on the connection mode among the processors. The representative connection modes for configuring the multicomputer are a point-to-point link connection mode shown in the accompanying FIG. 1 and a bus connection mode shown in the accompanying FIG. 2.
First, the point-to-point link connection mode shown in the accompanying FIG. 1 is an example for one dimensional array form connected by point-to-point links. To be brief, each of a plurality of unit computer in a certain array can transmit different messages at the same time since the respective links can independently effect the communications. Accordingly, the point-to-point link connection mode has the advantage of high communication network throughput.
On the other hand, in case of processing broadcasting messages in the point-to-point link connection mode shown in the accompanying FIG. 1, the link connection mode has the problem in which the throughput of communication network is abruptly reduced because it occupies many links at the same time. Moreover, since the link connection mode must sequentially occupy the required links, it would take long time necessary for communications.
Unlike the above-mentioned point-to-point link connection mode, the bus connection mode can effectively transmit urgent messages or broadcasting messages. The bus connection mode shown in FIG. 2 is an example for one dimensional array connected by buses capable of multi-accessing.
To be brief, since urgent message or broadcasting message is directly connected to a destination node computer only once bus request without passing through router of the intermediate path, it would take short time even when transmitting broadcasting message.
On the other hand, in unicast communication among the neighboring unit computers, the bus connection mode must occupy all the buses in a certain array, only one message can be processed in that array at the same time, thereby degrading the communication throughput.
Consequently, because the prior arts of typical connection modes have both conflicting merits and demerits, recently, a method for configuring multicomputer taking only their merits have been proposed. The typical methods include the technologies disclosed in U.S. Pat. No. 4,933,936 and the References(Reference 1 to Reference 3) as set forth below:
Reference 1: Q. Stout, Mesh-connected Computers with Broadcasting, IEEE Trans. Computers, C-32(9):826-830, September 1983.
Reference 2: M. Serrano and B Parhami, Optimal Architecture and Algorithms for Mesh-connected Parallel Computers with Separable Row/Column Buses, IEEE Trans. Parallel and Distributed Systems, 4(10):1073-1079, October 1993.
Reference 3: J. Duato, F. Silla, and S. Yalamanchili, A High Performance Router Architecture for interconnection Networks, 1996 International Conference on Parallel Processing, pp I-61-68, 1996.
To be brief on the above U.S. Pat. No. 4,933.936 and the References, the U.S. Pat. No. 4,933.936 describes on separate two physical network configurations, in which the broadcasting message is transmitted through the bus network and other messages are transmitted through the communication link of other path according to the types of communications via separate two communication paths in distributed environments.
Also, the Reference 1 describes on the effect(the reduction of performance time) obtainable upon adding a network for broadcasting to mesh computer, the Reference 2 describes on a method for performing semigroup and prefix computations by only a minimum network resource without a loss due to the complexity of the time in the computer connected in mesh architecture having row and column bus.
Finally, the Reference 3 describes on the architecture of router for transmitting data by adopting a wave pipelining transmission technique and thus forming a circuit with link from source node to destination node in unicast communication.
Referring to the above U.S. Pat. No. 4,933,936 and the References, they have the architecture comprising separate two communication networks as shown in the accompanying FIGS. 3 and 4.
FIG. 3 illustrates one dimensional array, and FIG. 4 illustrates the architecture of two dimensional mesh communication network having physical row and column bus. Each of nodes(N) shown in FIG. 4 is comprised of four channels connected to 16-bit shared buses (CBa to CBd and RBa to RBd) and a 16-bit unidirectional link(L). In this case, the respective nodes must have a switch for a point-to-point link and a transceiver for driving bus lines, however, there is the problem in which the speed of bus is slower than that of the point-to-point link due to fan-out limitation of the bus transceiver.
Therefore, in the above U.S. Pat. No. 4,933,936 and the prior arts disclosed in the References, the broadcasting messages and unicast transmission messages have been processed through each of separate two communication networks connected to one unit computer. Accordingly, this method would be expected to effectively use the resource of communication network only when the traffic of communication network is evenly distributed to separate two communication network.
However, when the traffic of communication network is concentrated into one type of communication network, the entire communication networks are in saturation even if other types of communication network can afford to process messages. Namely, because the bandwidth allocation to two communication networks is predefined in the design phase of communication network regardless of the types of task to perform, the problem in which the resources of communication network are wasteful has been arisen in most of programs expect for some defined application programs having communication pattern adapted for the assigned bandwidth.
Therefore, in order to overcome the problems encountered with the prior art, the object of the present invention is to provide a distributed computing system using virtual buses adapted for urgent messages or broadcasting messages transmitting a message to different computers at the same time as well as a point-to-point communication and enabling high speed processing on a large amount of the parallel simulations, real-time programs, or the like by introducing virtual buses into the connection architectures among the processors, and data communication method for the same.
In accordance with the present invention, the object is accomplished by providing a distributed computing system of one dimensional architecture having a predetermined number of routers, the connection among the respective routers being made in a point-to-point link, the respective routers being connected to each processor, the respective routers comprising: means for forming a direct data transmission path between an input terminal and an output terminal corresponding to the array dimension of the routers in order for the respective routers to use the point-to-point link connected with router adjacent to the respective routers as one virtual bus on specific condition; and row and column control lines wire-ORed with the respective routers according to one dimensional architecture in which the respective routers are arrayed for exchanging information among the respective routers, the control line being driven when the means for forming a direct data transmission path is driven to form the virtual buses.
In accordance with the present invention, another object is accomplished by providing a distributed computing system having a predetermined number of routers, the connection among the respective routers being made in a point-to-point link, the respective routers being connected to each processors, the respective routers comprising: means for forming a direct data transmission path between input terminal and output terminal corresponding to the array dimensional of the routers in order for the respective routers to use the point-to-point link connected with router adjacent to the respective routers as one virtual bus on specific condition; row and column control lines wire-ORed with the respective routers according to architecture in which the respective routers are arrayed for exchanging information among the respective routers; and two or more dimensional architecture with the distributed computing system of one dimensional array driven by the control line being arrayed and formed in a hierarchical connection architecture such as multi-dimensional mesh, hypercube and hierarchical ring when the means for forming a direct data transmission path is driven to form the virtual buses.
In accordance with the present invention, further another object is accomplished by providing a method for preventing link data from colliding with bus data when using link as virtual bus, in a distributed computing system comprising a predetermined number of routers being arrayed in mesh architecture, the connection among each of the routers being made in a point-to-point link, the respective routers including a direct data transmission path between an input terminal and an output terminal in row axis and column axis directions in order for the respective routers to use the point-to-point link connected with router adjacent to the respective routers as one virtual bus on specific condition; and row and column control lines wire-ORed with the respective routers according to row and column in which the respective routers are arrayed for exchanging information among the respective routers when the direct data transmission path included between the input terminal and the output terminal is driven to form the virtual buses, the method comprising the steps: a first step for detecting a bus busy signal on the row control line and column control line and determining whether the operation of the virtual bus has been issued; if it is determined that the operation of the virtual bus has been issued in the first step, a second step for determining whether or not a significant data exists on the link; if it is determined that the data exists in the second step, a third step for transmitting a signal meaning that data on the present link must be ignored from transmission side of the link data to reception side; a fourth step for transmitting a signal indicating the reception completion of the link data to the transmission side if the reception side receives and preserves the present link data before the reception side receiving the signal transmitted from the transmission side in the third step, and for not preserving the present link data if the reception side receives the signal transmitted from the transmission side in the third step before the link data being preserving in the reception side; and a fifth step for deleting the data preserved in the transmission side if the transmission side receives the reception completion signal of the link data transmitted from reception side to transmission side, and for preserving the transmitted data if the transmission side does not receive the reception completion signal of the link data transmitted from reception side to transmission side.
In accordance with the present invention, still another object is accomplished by providing a data communication method using virtual buses including a function for preventing collision between link data and bus data when forming the virtual buses in a distributed computing system, in the distributed computing system comprising a predetermined number of routers being arrayed in mesh architecture, the connection among each of the routers being made in a point-to-point link, the respective routers including a direct data transmission path between an input terminal and an output terminal in row axis and column axis directions in order for the respective routers to use the point-to-point link connected with router adjacent to the respective routers as one virtual bus on specific condition; and row and column control lines wire-ORed with the respective routers according to row and column in which the respective routers are arrayed for exchanging information among the respective routers when the direct data transmission path included between the input terminal and the output terminal is driven to form the virtual buses, the method comprising the steps: a first step for allowing a source router of a router trying to transmit data to select one mode of unicast communication mode, multicast communication mode, column broadcasting communication mode or broadcasting communication mode as the transmission mode of transmission data according to the kind of data or the position of a reception router; a second step for allowing the source router to request the use of a row or a column virtual bus according to the data communication mode selected by the first step; a third step for transmitting the data communication mode selected by the first step via the row or the column control line and informing the routers of it in the virtual bus if the bus grant is taken by the second step at the source router; a fourth step for proceeding all the routers on the virtual bus taking the bus grant after the third step except for the. source router to a link data freezing process; a fifth step for allowing the source router to transmit information related to a destination router(s) and bridge(s) via the formed virtual bus to set the destination router(s) and bridge(s); a sixth step for allowing each bridge to perform operations similar to the second to fourth steps so as to form the virtual bus to the destination router(s) according to the information of the destination router(s) transmitted from the source router when the bridge is set through the fifth step; and a seventh step for transmitting data at the source router if the virtual bus is formed through the sixth step between the source router and the destination router(s).